package src.CodeTop;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
 *
 *  
 *
 * 示例 1：
 *
 *
 * 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
 * 输出：[1,2,3,6,9,8,7,4,5]
 * 示例 2：
 *
 *
 * 输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
 * 输出：[1,2,3,4,8,12,11,10,9,5,6,7]
 *
 */

public class _54SpiralMatrix {
    public static void main(String[] args) {

    }

    public List<Integer> spiralOrder(int[][] matrix) {
        // 定义最后的结果数组
        ArrayList<Integer> target = new ArrayList<>();
        // 如果矩阵为空则直接返回
        if (matrix.length == 0) {
            return target;
        }
        // 定义动态数组所需最大长度
        int maxLength = matrix.length * matrix[0].length;
        // 定义结果数组的索引
        int index = 0;
        // 定义左上角的行和列，右下角的行和列
        int leftUpRow = 0, leftUpColumn = 0, rightDownRow = matrix.length - 1, rightDownColumn = matrix[0].length - 1;
        // 循环打印，退出条件是两个顶点交错一定会有这种情况)
        while (leftUpColumn <= rightDownColumn && leftUpRow <= rightDownRow) {
            int r = leftUpRow, c = leftUpColumn;
            // 输出矩阵的最上面一条边
            while (c <= rightDownColumn) {
                if (index >= maxLength){
                    break;
                }
                target.add(matrix[r][c++]);
                index++;
            }
            if (index >= maxLength){
                break;
            }
            // 恢复下标
            c = rightDownColumn;
            r++;
            // 最右边的一条边
            while (r <= rightDownRow) {
                if (index >= maxLength){
                    break;
                }
                target.add(matrix[r++][c]);
                index++;
            }
            if (index >= maxLength){
                break;
            }
            // 恢复
            r = rightDownRow;
            c--;
            // 最下面一条边
            while (c >= leftUpColumn) {
                if (index >= maxLength){
                    break;
                }
                target.add(matrix[r][c--]);
                index++;
            }
            if (index >= maxLength){
                break;
            }
            // 恢复
            c = leftUpColumn;
            r--;
            // 最左边一条边(不包含之前已遍历部分)
            while (r > leftUpRow) {
                if (index >= maxLength){
                    break;
                }
                target.add(matrix[r--][c]);
                index++;
            }
            if (index >= maxLength){
                break;
            }
            // 打印完后r和c都会回到左顶角
            // 这个时候左上顶点和右下顶点都要往中间走一下
            leftUpColumn++; leftUpRow++; rightDownColumn--; rightDownRow--;
        }
        return target;
    }
}
